Some conventional secure computer systems protect a secret by distributing shares of the secret to a group of clients. The clients are then able to recover the secret only when at least a threshold number of the clients combine their shares. For example, suppose that the secret to be protected is a number, and that at least m clients are required for recovering the secret. A computer system configured to protect the secret, known as a dealer, generates a polynomial f(x) of degree m−1 such that the secret is the constant term of that polynomial, f(0). The dealer then distributes one of the quantities f(1), f(2), . . . , f(n), to each client when there are n clients. In this way, any m of the n clients can recover the secret using Lagrange interpolation.
Other conventional computer systems proactively update the shares of the secret at regular intervals. To continue the above example, the dealer generates another polynomial g(x) of degree m−1 such that g(0)=0. The constant term of a new polynomial (f+g)(x), also of degree m−1, also reveals the secret. The dealer then distributes one of the quantities g(1), g(2), . . . , g(n), to each client, any m of the n clients recovering the secret using Lagrange interpolation on each of their values of f+g.
It should be understood that there are other ways to split a secret into shares. For example, the secret may be split into shares such that an exclusive or (XOR) operation on all of the shares recovers the secret. In this case, the shares of the same secret can be adjusted by updating two or more shares in such a way as to preserve the secret.
Often, also, in other computer systems one or more secrets, some of which may themselves be possibly shared amongst groups of clients, need be updated. Those secrets that are shared can be updated by updating one or more of the shares they are dispersed into.
In many cases, the dealer is not trusted by the clients to distribute updates that are able to recover the secret. In such a case, the clients themselves may provide updates to each other's shares at the regular intervals.